/**
 * @Question.Title: 将 x 减到 0 的最小操作数
 * @Question.No: 1658
 * @Author: DQ
 * @Date: 2021-02-05 14:18:32
 * @Description: 
 */
//给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改
// 数组以供接下来的操作使用。 
//
// 如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,1,4,2,3], x = 5
//输出：2
//解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [5,6,7,8,9], x = 4
//输出：-1
// 
//
// 示例 3： 
//
// 
//输入：nums = [3,2,20,1,1,3], x = 10
//输出：5
//解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 105 
// 1 <= nums[i] <= 104 
// 1 <= x <= 109 
// 
// Related Topics 贪心算法 双指针 二分查找 Sliding Window 
// 👍 46 👎 0

package slidingwindows.leetcode.editor.cn;

public class MinimumOperationsToReduceXToZero {
    public static void main(String[] args) {
        Solution solution = new MinimumOperationsToReduceXToZero().new Solution();
        int[] nums = {5,6,7,8,9};
    }
        //leetcode submit region begin(Prohibit modification and deletion)
        class Solution {
            public int minOperations(int[] nums, int x) {
                // 将要移除的左右边的指针
                int left=0, right=nums.length-1;
                int min = Integer.MAX_VALUE;;
                while(x-nums[left]>=0&&left<nums.length){
                    x -= nums[left++];
                }
                int tmp = left;
                if(x==0) min = min < tmp ? min : tmp;
                // 此时的left为可以移除的左边的最后一个指针的后一个
                while(right>=left){
//                System.out.printf("(%d,%d)\n",left,right);
                    //能吃下去
                    if(x-nums[right]>=0) {
                        x-=nums[right--];
                        tmp++;
                        if(x==0) min = min < tmp ? min : tmp;
                    }else {//吃不下去，就将左边的吐出来
                        if(left==0) break;
                        x += nums[--left];
                        tmp--;
                    }


                }

                return min==Integer.MAX_VALUE?-1:min;
            }
        }
//leetcode submit region end(Prohibit modification and deletion)

}